package April.递增顺序搜索树0425;





   class TreeNode {
      int val;
      TreeNode left;
     TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
          this.right = right;
      }
  }

public class Solution {
    // public TreeNode increasingBST(TreeNode root) {
    //     List<Integer> res = new ArrayList<Integer>();
    //     inorder(root, res);

    //     TreeNode dummyNode = new TreeNode(-1);
    //     TreeNode currNode = dummyNode;
    //     for (int value : res) {
    //         currNode.right = new TreeNode(value);
    //         currNode = currNode.right;
    //     }
    //     return dummyNode.right;
    // }

    // public void inorder(TreeNode node, List<Integer> res) {
    //     if (node == null) {
    //         return;
    //     }
    //     inorder(node.left, res);
    //     res.add(node.val);
    //     inorder(node.right, res);
    // }
    public TreeNode increasingBST(TreeNode root) {
        if (root == null) return null;
        // 得到以root左节点为根节点的递增顺序搜索树
        TreeNode left = increasingBST(root.left);
        // 得到以root右节点为根节点的递增顺序搜索树
        root.right = increasingBST(root.right);
        // 如果左节点为空，则直接返回root
        if (left == null) return root;
        // 找到left末端结点
        TreeNode node = left;
        while (node.right != null) {
            node = node.right;
        }
        root.left = null;
        // 把root接到left的末端
        node.right = root;
        return left;
    }

}
